448. Find All Numbers Disappeared in an Array

Similar Question

442. Find All Duplicates in an Array

268. 丢失的数字 - 力扣（LeetCode）

Solution Tips

原地标记

Arithmetic-progression

对应 1 - n 的 index，被转换为负数的就是存在的数，没有被转换为负数的值对应的 index 就是不存在的数。

原地标记，把空间复杂度降到最低。

  var findDisappearedNumbers = function(nums) {
    const len = nums.length
    for (let i = 0; i < len;i++) {
      const index = Math.abs(nums[i]) - 1
      nums[index] = -Math.abs(nums[index])
    }
    // [-4,-3,-2,-7,8,2,-3,-1]
    const res = []
    for (let i = 0; i < len; i++) {
      if(nums[i]>0){
        res.push(i+1)
      }
    }
    return res
  }
  let nums = [4,3,2,7,8,2,3,1]
  console.log(findDisappearedNumbers(nums))

Hash-table

var findDisappearedNumbers = function(nums) {
    const n = nums.length;
    const hashTable = new Array(n + 1).fill(undefined);
    hashTable[0] = 0;

    for (let i = 0; i < nums.length; i++) {
        const num = nums[i];
        if (hashTable[num] === undefined) {
            hashTable[num] = num;
        }
    }

    const res = [];

    for (let i = 0; i < hashTable.length; i++) {
        const item = hashTable[i];
        if (item === undefined) {
            res.push(i);
        }
    }

    return res;
};